在上上篇博客中，我们介绍了算法中中的查找算法，其中大部分是在介绍查找算法中需要用得到的数据结构。在这一篇博客中，我们将来开启图的新篇章。

图的源码

在前面我们所介绍的树的数据结构中，我们可以明显的感觉到，树的表示是分层的，例如父子关系，而其他关系只能间接的表示，例如同级关系。而图却不受这种限制。图是由顶点（或结点）及顶点之间的关系组成的集合。通常，图中的顶点数量或者一个顶点与其他顶点之间的连线的个数不受限制。（C++数据结构与算法）

主要有以下两种定义。 二元组的定义： 图G是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与V不相交。它们亦可写成V(G)和E(G)。 E的元素都是二元组，用(x,y)表示，其中x,y∈V。 三元组的定义： 图G是指一个三元组(V,E,I)，其中V称为顶集，E称为边集，E与V不相交；I称为关联函数，I将E中的每一个元素映射到 。如果e被映射到(u,v)，那么称边e连接顶点u,v，而u,v则称作e的端点，u,v此时关于e相邻。同时，若两条边i,j有一个公共顶点u，则称i,j关于u相邻。

在介绍图之前，首先让我们来了解一下图中的一个重要的分类。图的术语特别的多，不过我们可以慢慢的了解，因为定义都比较简单（我将在下面慢慢的介绍一些术语）。

无向图：图是有一组顶点和一组能够将两个顶点相连的边组成的。可能概念有点模糊，但是可以根下面的有向图相比较就特别简单了。

有向图：由一组顶点和一组有方向的边组成，每条有方向的边都连接着有序的一对顶点

（这张来自百度百科的图片都快糊了）

图的分类其实很多，但是我们主要介绍的就是这两种分类，还有一些分类可能会在接下来的博客中提到（我也不确定会不会提到，还没写）

相邻：如果两个顶点通过一条边相连， 则称这两个顶点是相邻的，并称这条边依附于这两个顶点

度数：某个顶点的度数即为依附于它的边的总数。

子图：一幅图的所有边的一个子集以及他们所依附的所有顶点组成的图。

路径：由边顺序链接的一系列顶点。

简单路径：一条没有重复顶点的路径。

环：一条至少包含一条边且起点和终点相同的路径。

简单环：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的环。

连通图：任意两个顶点之间互通。一副非连通的图由诺干个连通的部分组成。

图的密度：已连接的顶点对占所有可能被连接的顶点对的比例。

平行边：连接同一对顶点的两条边称为平行边。

二分图：图中的每一条边所连接的两个顶点都分别属于不同的部分，如下图所示：

在这一章博客中，我所讲的内容会偏向于算法，并不会在数据结构上面说很多内容。

OK，在前面说完这么多，首先让我们来说下最简单的图：无向图

不过在说在无向图的操作之前，我们至少得解决一个问题：我们使用如何的结构去储存图。在前面我们知道，图不是像树一样（绝大部分的树），只需要关心父子关系，而不需要关心兄弟关系。简单点来说，就是树的关系是纵向的（从上到下），而图却并不是这样，图之间的关系是并列的。相信看过图这种数据结构的人，应该对于图的储存结构的方式可以说的信口拈来吧。下面是一些图的储存的方法：

图源：geeksforgeeks

邻接矩阵表示法

下图一眼就可以看懂，如果结点a与结点b之间相连接，则A(a,b) = A(b,a) = 1，否则为0。

邻接表表示法

在邻接表表示法中，第一列代表的为结点，如0,1,2……，而后面的则代表为结点与其他结点相连接的结点。（例如0结点后面为1,4结点，则代表0结点与1结点和4结点相连接【在这里我们可以发现，第5行的4结点的后面同样有1结点】）

关联矩阵表示法

那么我们该选择哪一种的表示方式呢？两种各有优缺点：

如果我们需要处理顶点V的邻接顶点，我们使用邻接表只需要deg(v)步操作（deg:图论中点连出的边数）。而在邻接矩阵中，我们需要进行|V|步操作。但是在当我们需要插入或者删除一个邻接与v的节点的时候，我们需要对邻接表进行调整，而对于邻接矩阵，只需要进行0和1的变换即可。

邻接矩阵的空间复杂度是O(V*V)，而邻接表的复杂度为O(V+E)，V为顶点数，E为边数。

我们将会遇到的应用使用几乎都是稀疏图——《算法第四版》

​ 在这里我们可以再想一下，在最稠密的情况下（每一个结点都与其他结点相连接），邻接矩阵的空间复杂度会远远的 小于邻接表（n!和n^2不在一个数量级）。

说了这么多，在下面的数据结构中，除非特殊说明，我们选择使用邻接表来进行数据储存。我们可以上代码了。

首先是抽象类的代码：

下面是一张过程示意图（左边是对G2进行逆后序排序，右边是根据排序的结果进行深度递归）

在说最小生成树之前，我们得先来说说加权图。下图中便是一副加权无向图。加权图和图的区别在于它的每一条边都有一个权值，那么它有什么用呢？举个栗子：图我们可以应用在网络流量方面，那么每一条边的h权值可以代表某一时刻的网络质量，那么当流量进行选择的时候，肯定会选择质量好的那一路。（实际上网络流量选择要比这还复杂，因为还要考虑到负载均衡的情况。）

那么什么是最小生成树呢?

图的生成树是它的一棵含有其所有顶点的无环连通子图。

一幅加权图的**最小生成树（MST）**是它的一棵权值（树的所有边的权值之和）最小的生成树。如上图的黑色边构成的无环连通子图。在这里我们规定：

下面是生成树的一些性质：

如下图：

根据上面的两个性质，我们可以将图中所有的顶点切分为两个非空且不重叠的两个集合。而其中横切边是一条连接两个属于不同集合的顶点的边。

切分定理：把加权图中的所有顶点分为集合、检查横跨两个集合的所有边并识别哪条边应属于图的最小生成树。

当然，在切分中，我们会得到一条权重最小的边（这条边必然属于最小生成树的边），但是并不代表着其它的边就不属于最小生成树。

切分定理是解决最小生成树问题的所有算法的基础。而这些算法都是贪心算法的特殊情况：使用切分定理找到一条边，然后不断的切分，直到找出所有的最小生成树的所有边。

最小生成树的贪心算法：我们将含有V个顶点的加权连通图的最小生成树的边标记为黑色（初始状态边是灰色的），找到一种切分，它产生的横切边均不为黑色，然后权重最小的横切变标记为黑色。反复，直到标记了V-1条黑色边为止。

下面是一个贪心最小生成树算法的图：

因为有权无向图的边发生了改变，所以定义数据结构的代码也得发生改变。

带权重的边的数据类型

加权无向图的数据类型：

在定义好数据结构后，我们就可以开始来说一下生成最小树的算法了

最小生成树的算法

对于最小生成树有两种常用的算法，普里姆算法（Prim算法）和克鲁斯卡尔算法（Kruskal算法）。这两种算法都是基于贪心算法的算法。首先让我们来说一下Kruskal算法，这个比较简单。

Kruskal算法很简单，首先我们得到所有的边，然后根据边的权重对边进行排序（从小到大）。然后我们将边根据顺序加入最小生成树中（必须保证加入的边不会与已经加入的边构成环）

现在这个问题就分成了两个部分：

我们来着重讨论第二点，如何检测回路

如何检测回路，我们可以使用union-find算法。首先我们说一下这个的原理：

首先我们有N个独立分散的点，如果我们将点用线段进行连接，如何避免成环。我们可以这样想，，像树一样，有根节点，如果两个结点的根节点是一样的，那么毋庸置疑，将两个结点进行连接肯定会成环。

其中，这个算法有3种写法：

我将介绍加权quick-union算法，因为这个在最最坏的情况下时间复杂度也只有lgN。

quick-union算法